package main

import "fmt"

// 我们都知道，分割算法是快排的核心
// 网上和书里分割函数有很多，有些弄得复杂了。
// 比如: https://www.jianshu.com/p/1335fb7f96ea ; https://blog.csdn.net/qq_29542611/article/details/79859565
//
// 这里分割的时候：只保证一个原则， 那就是把比基准小的数据都移到左边
func partition(a []int, p, q int) int {
	pivot := a[q]
	nextLowerIndex := p // nextLowerIndex 表示分割中， 小于pivot的值下一个位置；结束分割时，将pivot的值和它对于的值做交换， 即可实现分割

	zprint := func() {
		fmt.Println(a[p:q+1], "p=", p, "q=", q, "nextLowerIndex=", nextLowerIndex, "a[nextLowerIndex]=", a[nextLowerIndex], "pivot", pivot)
	}
	zprint()
	for j := p; j < q; j++ {
		if a[j] < pivot {
			a[j], a[nextLowerIndex] = a[nextLowerIndex], a[j]
			nextLowerIndex++
			zprint()

		}
	}
	a[nextLowerIndex], a[q] = a[q], a[nextLowerIndex]
	zprint()
	fmt.Println("part end.")
	return nextLowerIndex
}

func qs(a []int, p, q int) {
	if p >= q {
		return
	}
	index := partition(a, p, q)
	qs(a, p, index-1)
	qs(a, index+1, q)
}

func main() {
	a := []int{19, 11, 12, 13, 14, 15, 16, 17, 18}
	qs(a, 0, len(a)-1)
	fmt.Println(a)
}
